/**
 * @file     search.ts
 * @brief    [33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/description/)
 * @author   Zhu
 * @date     2022-11-15 22:45
 */

/**
 * 二分，必有一单调区间，和一不确定区间
 * 不停地二分以找到单调区间，判断target在不在单调区间
 * 1. 确定单调区间的上下界
 * 2. 注意单调区间的边界等号
 */
function search(nums: number[], target: number): number {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left;
        if (nums[mid] === target) return mid;

        // left
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // right
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}
